package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * description:
 * author:张腾
 * date:2021-06-06
 */

/**
 * 已知前序遍历和中序遍历，求树
 */
public class leetcode105 {
    Map<Integer,Integer> map = new HashMap<>();
    int[] preOrder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preOrder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }

        return build(0,0,preorder.length-1);
    }

    public TreeNode build(int pre_head, int left, int right){
        if (left>right) return null;

        TreeNode root = new TreeNode(preOrder[pre_head]);
        int index = map.get(preOrder[pre_head]);

        root.left = build(pre_head+1,left,index-1);
        root.right = build(pre_head+index-left+1,index+1,right);

        return root;
    }

}
